#ifndef QUICKSORT_H
#define QUICKSORT_H
#include<bits/stdc++.h>




template <typename Comparable>
void sort(std::vector<Comparable>& A);
//template <typename Comparable>
//void quicksort(std::vector<Comparable>& A);
template <typename Comparable>
void quicksort(std::vector<Comparable>& A, int left, int right);
template <typename Comparable>
//void partition(std::vector<Comparable>& A);
//template <typeneme Comparable>
void insertionsort(std::vector<Comparable>& A, int left, int right);
template <typename Comparable>
const Comparable & median3( vector<Comparable> & A, int left, int right );

template <typename Comparable>
void sort(std::vector<Comparable>& A)
{
  if( A.size() <= 10 )//10以内用插入排序
    {
      insertionsort( A, left, right );
      return;
    }
  else//大于10则用快速排序
    {
      double result;
      clock_t start, end;
      start = clock();
      quicksort( A, left, right );
      end=clock();
      result = (end - start)/CLOCKS_PER_SEC;
      return result;
    }
}

template <typename Comparable>
void insertionsort(std::vector<Comparable>& A,  int left, int right )//插入排序
{
  auto length = A.size();
  auto val1 = A.begin();
  for( ; val1< A.end(); val1++ )
    {
      Comparable temp = std::move( *val1 );
      for(auto val2 = A.begin(); val2 < val1; val2++)
	{
	  if( *val2 > temp )
	    {
	      for(auto val3 = val1; val3 > val2; val3--)
		{
		  *val3 = *(val3-1);
		}
	      *val2 = temp;
	      break;
	    }
	}
    }
  
}

//template <typename Comparable>
//void quicksort(std::vector<Comparable>& A)
//{
//  quicksort( A, 0, A.size() - 1 );
//}

template <typename Comparable>
void quicksort( vetcor<Comparable>& A, int left, int right )
{
      Comparable privot = median3( A, left, right );
      int i = left, j = right - 1;
      for(; ;)
	{
	  while( A[++i] < pivot ){}
	  while( pivot < A[--j] ){}
	  if( i<j )
	    {
	      swap( A[i], A[j] );
	    }
	  else
	    break;
	  
	}
      swap( A[i], A[right - 1]);

      quicksort( A, left, i-1 );
      quicksort( A, i+1, right);
    }
}

template <typename Comparable>
const Comparable & median3( vector<Comparable>& A, int left, int right )
{
  int center = ( left + right ) / 2;
  if( A[center] < A[left] )
    swap( A[left], A[center]);
  if( A[right] < A[left])
    swap( A[left], A[right]);
  if( A[right] < A[center] )
    swap( A[center] ,A[right]);

  swap( A[center], A[right-1]);
  return A[right-1];
}


#endif
